/**
 * Creat with IntelliJ IDEA
 * Description
 * User: mamba24
 * Date: 2022-04-30
 * Time: 23:33
 * To BE A Better Person-2020-3-2
 */
class MyLinkedList {

     static class Node{
       public int val;
       public Node next;
         public Node(int val) {
             this.val = val;
         }
     }

     public Node head ;
     public void CreateNode(){
         Node n1=new Node(1);
         Node n2=new Node(2);
         Node n3=new Node(3);
         Node n4=new Node(3);
         Node n5=new Node(5);
         Node n6=new Node(3);
         n1.next=n2;
         n2.next=n3;
         n3.next=n4;
         n4.next=n5;
         n5.next=n6;
         this.head=n1;
     }
     //头插法
    public void addFirst(int data){
        if(this.head==null){
            Node n=new Node(data);
            this.head=n;
        }else {
            Node n=new Node(data);
            n.next=this.head;
            this.head=n;
        }
    }
     //尾插法
    public void addLast(int data){
        if(this.head==null){
            Node n=new Node(data);
            this.head=n;
        }else {
            Node n=new Node(data);
            Node cur = head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=n;
        }
    }
    //计算链表长度
    private int CalSize(){
         int size=0;
         Node cur=this.head;
         while(cur!=null){
             cur=cur.next;
             size++;
         }
         return size;
    }
    //判断下标是否合法
    private boolean IndexInBoundary(int index){
         if(index > CalSize() || index < 0) {
             return false;
         }else{
             return true;
         }
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
         boolean i = IndexInBoundary(index);
         if(i==false){
             System.out.println("error index");
             return false;
         }else {
             if(head==null){
                 Node n=new Node(data);
                 head=n;
             }else{
                 int id=1;
                 Node n=new Node(data);
                 Node cur=this.head;
                 while(id!=index){
                     cur=cur.next;
                     id++;
                 }
                 n.next=cur.next;
                 cur.next=n;
             }

         }
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur =this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    //hhhh
    public void remove(int key){
        Node cur = this.head;
        Node prev = cur;
        if(this.head == null) {
            System.out.println("empty");
            return;
        }else{
            while(cur != null) {
                if(cur.val == key) {
                    break;
                }
                prev = cur;
                cur = cur.next;
            }
            prev.next = cur.next;
        }

    }
    //反转链表
    //hhh
    //hhh
    public void reverseList() {
        Node cur=this.head.next;;
        Node prev=cur.next;
        this.head.next=null;
        while(prev.next != null) {
            cur.next=this.head;
            this.head=cur;
            cur=prev;
            prev=prev.next;
        }
        prev.next=cur;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        Node cur=this.head.next;
        Node prev=this.head;
        while(cur != null) {
            if(cur.val == key) {
                prev.next=cur.next;
                cur=cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val==key){
            this.head=this.head.next;
        }
    }

    public void display(){
         Node cur=this.head;
         while(cur != null){
             System.out.print(cur.val+" ");
             cur=cur.next;
         }
    }
    public void clear(){
        this.head = null;
    }
}
//hhhh
public class TestDemo {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.CreateNode();
        myLinkedList.display();
        System.out.println();
        System.out.println("==========");
        myLinkedList.reverseList();
        myLinkedList.display();
    }
    public static void main1(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.CreateNode();
        myLinkedList.display();
        myLinkedList.addFirst(99);
        System.out.println();
        myLinkedList.display();
        System.out.println();
        myLinkedList.addLast(7);
        myLinkedList.display();
        myLinkedList.addIndex(3,7);
        System.out.println();
        boolean i=myLinkedList.contains(4);
        myLinkedList.display();
        System.out.println(i);
        myLinkedList.remove(4);
        myLinkedList.remove(7);
        myLinkedList.display();
    }
}
